目前个人电脑的（ ）市场占有率最靠前的厂商包括Intel、AMD等公司。

无论是TCP/IP模型还是OSI模型，都可以视为网络的分层模型，每个网络协议都会被归入某一层中。如果用现实生活中的例子来比喻这些“层”，以下最恰当的是（ ）。

以下不属于目前 3G（第三代移动通信技术）标准的是（ ）。

如果不在快速排序中引入随机化，有可能导致的后果是（ ）。

仿生学的问世开辟了独特的科学技术发展道路。人们研究生物体的结构、功能和工作原理，并将这些原理移植于新兴的工程技术之中。以下关于仿生学的叙述，错误的是（ ）。（2012年提高组初赛）

在程序运行过程中，如果递归调用的层数过多，会因为（ ）引发错误。

1946年诞生于美国宾夕法尼亚大学的ENIAC属于（ ）计算机。

（ ）是主要用于显示网页服务器或者文件系统的 HTML 文件内容，并让用户与这些文件交互的一种软件。

目前计算机芯片（集成电路）制造的主要原料是（ ），它是一种可以在沙子中提炼出的物质。（2012年提高组初赛）

地址总线的位数决定了 CPU 可直接寻址的内存空间大小，例如地址总线为 16 位，其最大的可寻址空间为 64KB。如果地址总线是 32 位，则理论上最大可寻址的内存空间为（ ）。

十进制下的无限循环小数（不包括循环节内的数字均为 0 或均为 9 的平凡情况），在二进制下有可能是（ ）。

在计算机显示器所使用的 RGB 颜色模型中，（ ）属于三原色之一。

逻辑异或（⊕）是一种二元运算，其真值表如下所示。

以下关于逻辑异或的性质，正确的有（ ）。

如果对于所有规模为 n 的输入，一个算法均恰好进行（ ）次运算，我们可以说该算法的时间复杂度为 O(2n)。

从顶点 A0出发，对有向图（ ）进行广度优先搜索（BFS）时，一种可能的遍历顺序是 A0, A1, A2, A3, A4。

一棵二叉树一共有 19 个节点，其叶子节点可能有（ ）个。

以下关于计算复杂度的说法中，正确的有（ ）。

已知带权有向图 G 上的所有权值均为正整数，记顶点 u 到顶点 v 的最短路径的权值为d(u, v)。若 v1, v2, v3, v4, v5是图 G 上的顶点，且它们之间两两都存在路径可达，则以下说法正确的有（  ）。

如果一个栈初始时为空，且当前栈中的元素从栈底到栈顶依次为a, b, c（如右图所示），另有元素 d 已经出栈，则可能的入栈顺序有（ ）。

以下（ ）属于互联网上的 E-mail 服务协议。

本题中，我们约定布尔表达式只能包含 p, q, r 三个布尔变量，以及“与”（∧）、“或”（∨）、“非”（¬）三种布尔运算。如果无论 p, q, r 如何取值，两个布尔表达式的值总是相同，则称它们等价。例如，(p∨q)∨r 和 p∨(q∨r)等价，p∨¬p 和 q∨¬q 也等价；而 p∨q 和 p∧q 不等价。那么，两两不等价的布尔表达式最多有         个。

对于一棵二叉树，独立集是指两两互不相邻的节点构成的集合。例如，图1有5个不同的独立集（1个双点集合、3个单点集合、1个空集），图2有14个不同的独立集。那么，图3有       个不同的独立集。

#include <iostream>
#include <string> 
using namespace std;

int lefts[20], rights[20], father[20]; 
string s1, s2, s3;
int n, ans;

void calc(int x, int dep)
{
	ans = ans + dep*(s1[x] - 'A' + 1);
	if (lefts[x] >= 0) calc(lefts[x], dep+1); 
	if (rights[x] >= 0) calc(rights[x], dep+1);
}
void check(int x)
{
	if (lefts[x] >= 0) check(lefts[x]); 
	s3 = s3 + s1[x];
	if (rights[x] >= 0) check(rights[x]);
}
void dfs(int x, int th)
{
	if (th == n)
	{
		s3 = "";
		check(0);
		if (s3 == s2)
		{
			ans = 0;
			calc(0, 1); 
			cout<<ans<<endl;
		}
		return;
	}
	if (lefts[x] == -1 && rights[x] == -1)
	{
		lefts[x] = th; 
		father[th] = x; 
		dfs(th, th+1); 
		father[th] = -1;
		lefts[x] = -1;
	}
	if (rights[x] == -1)
	{
		rights[x] = th; 
		father[th] = x; 
		dfs(th, th+1); 
		father[th] = -1;
		rights[x] = -1;
	}
	if (father[x] >= 0)
		dfs(father[x], th);
}
int main()
{
	cin>>s1; 
	cin>>s2;
	n = s1.size();
	memset(lefts, -1, sizeof(lefts));
	memset(rights, -1, sizeof(rights));
	memset(father, -1, sizeof(father));
	dfs(0, 1);
}

输入：

ABCDEF 

BCAEDF

输出：              

#include <iostream> 
using namespace std;

const int SIZE = 20;

int data[SIZE]; 
int n, i, h, ans;

void merge()
{
	data[h-1] = data[h-1] + data[h]; 
	h--;
	ans++;
}
int main()
{
	cin>>n; 
	h = 1;
	data[h] = 1;
	ans = 0;
	for (i = 2; i <= n; i++)
	{
		h++;
		data[h] = 1;
		while (h > 1 && data[h] == data[h-1]) 
			merge();
	}
	cout<<ans<<endl;
}

（1） 输入：8

输出：           （4 分）

（2） 输入：2012

输出：           （4 分

#include <iostream> 
using namespace std;

int n, i, ans;

int gcd(int a, int b)
{
	if (a % b == 0) 
		return b;
	else
		return gcd(b, a%b);
}
int main()
{
	cin>>n; 
	ans = 0;
	for (i = 1; i <= n; i++) 
		if (gcd(n,i) == i)
			ans++; 
	cout<<ans<<endl;
}

输入：120 

输出：            

#include <iostream> 
using namespace std;

int n, i, temp, sum, a[100];

int main()
{
	cin>>n;
	for (i = 1; i <= n; i++) 
		cin>>a[i];
	for (i = 1; i <= n - 1; i++) 
		if (a[i] > a[i + 1]) {
			temp = a[i]; 
			a[i] = a[i + 1]; 
			a[i + 1] = temp;
		}
	for (i = n; i >= 2; i--)
		if (a[i] < a[i - 1]) { 
			temp = a[i];
			a[i] = a[i - 1];
			a[i - 1] = temp;
		}
	sum = 0;
	for (i = 2; i <= n - 1; i++) 
		sum += a[i];
	cout<<sum / (n - 2)<<endl; 
	return 0;
}

输入：

8

40 70 50 70 20 40 10 30

输出：

（排列数）输入两个正整数 n, m (1 ≤ n ≤ 20, 1 ≤ m ≤ n)，在 1~n 中任取 m 个数，按字典序从小到大输出所有这样的排列。例如

输入：3 2

输出：

1 2

1 3

2 1

2 3

3 1

3 2

#include<iostream>

#include<cstring> 

using namespace std;

const int SIZE = 25;

bool used[SIZE]; 

int data[SIZE];

int n, m, i, j, k; 

bool flag;

int main()

{

cin>>n>>m;

memset(used, false, sizeof(used)); 

for (i = 1; i <= m; i++)

{

data[i] = i; 

used[i] = true;

}

flag = true; 

while (flag)

{

for (i = 1; i <= m-1; i++) cout<<data[i]<<" "; 

cout<<data[m]<<endl;

flag =      ①      ;

for (i = m; i >= 1; i--)

{

                ②               ;

for (j = data[i]+1; j <= n; j++) if (!used[j])

{

used[j] = true; 

data[i] =       ③      ; 

flag = true;

break;

}

if (flag)

{

for (k = i+1; k <= m; k++)

for (j = 1; j <=      ④      ; j++) if (!used[j])

{

data[k] = j; 

used[j] = true; 

break;

}

              ⑤            ;

}

}

}

}

（新壳栈）小 Z 设计了一种新的数据结构“新壳栈”。首先，它和传统的栈一样支持压入、弹出操作。此外，其栈顶的前 c 个元素是它的壳，支持翻转操作。其中，c > 2 是一个固定的正整数，表示壳的厚度。小 Z 还希望，每次操作，无论是压入、弹出还是翻转，都仅用与 c 无关的常数时间完成。聪明的你能帮助她编程实现“新壳栈”吗？

程序期望的实现效果如以下两表所示。其中，输入的第一行是正整数 c，之后每行输入都是一条指令。另外，如遇弹出操作时栈为空，或翻转操作时栈中元素不足 c 个，应当输出相应的错误信息。

#include <iostream> 

using namespace std;

const int

NSIZE = 100000,

CSIZE = 1000;

int n, c, r, tail, head, s[NSIZE], q[CSIZE];

//数组 s 模拟一个栈，n 为栈的元素个数

//数组 q 模拟一个循环队列，tail 为队尾的下标，head 为队头的下标

bool direction, empty;

int previous(int k)

{

if (direction)

return ((k + c - 2) % c) + 1; 

else

return (k % c) + 1;

}

int next(int k)

{

if (direction)

         ①        ;

else

return ((k + c - 2) % c) + 1;

}

void push()

{

int element;

cin>>element;

if (next(head) == tail) { 

n++;

                          ②        ;

tail = next(tail);

}

if (empty)

empty = false; 

else

head = next(head);

       ③        = element;

}

void pop()

{

if (empty) {

cout<<"Error: the stack is empty!"<<endl; 

return;

}

cout<<      ④       <<endl; 

if (tail == head)

empty = true; 

else {

head = previous(head); 

if (n > 0) {

tail = previous(tail);

                 ⑤            = s[n];

n--;

}

}

}

void reverse()

{

int temp;

if (      ⑥      == tail) { 

direction = !direction; 

temp = head;

head = tail; 

tail = temp;

}

else

cout<<"Error: less than "<<c<<" elements in the stack!"<<endl;

}

int main()

{

cin>>c; 

n = 0;

tail = 1;

head = 1; 

empty = true;

direction = true; 

do {

cin>>r; 

switch (r) {

case 1: push(); break;

case 2: pop(); break; 

case 3: reverse(); break;

}

} while (r != 0); 

return 0;

}